#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
#include<random>
using namespace std;

enum Color
{
	RED,
	BLACK
};

template<class K, class T>
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(RED)
	{}

	RBTreeNode<K, T>* _left;
	RBTreeNode<K, T>* _right;
	RBTreeNode<K, T>* _parent;
	T _data;
	Color _col;
};

template<class K,class T,class KeyofT>
class RBTree
{
public:
	typedef RBTreeNode<K, T> Node;

	//迭代器实现
	template<class Y, class Ref, class Ptr>
	struct RBTreeIterator
	{
		typedef RBTreeIterator<Y, Ref, Ptr> Self;

		Node* _node;
		RBTreeIterator(Node* node)
			:_node(node)
		{}

		Ref	operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}

		Self& operator++()
		{
			Node* cur = _node;
			if (cur->_right)
			{
				cur = cur->_right;
				while (cur->_left)
					cur = cur->_left;
				_node = cur;
			}
			else
			{
				while (cur->_parent && cur == cur->_parent->_right)
				{
					cur = cur->_parent;
				}
				cur = cur->_parent;
				_node = cur;
			}
			return *this;
		}

		Self operator++(int)
		{
			Node* cur = _node;
			Node* old = _node;
			if (cur->_right)
			{
				cur = cur->_right;
				while (cur->_left)
					cur = cur->_left;
				_node = cur;
			}
			else
			{
				while (cur->_parent && cur == cur->_parent->_right)
				{
					cur = cur->_parent;
				}
				cur = cur->_parent;
				_node = cur;
			}
			return Self(old);
		}

		bool operator!=(const Self& it)
		{
			return this->_node != it._node;
		}

		bool operator==(const Self& it)
		{
			return this->_node == it._node;
		}
	};

	typedef RBTreeIterator<T, T&, T*> iterator;


	//迭代器开始
	iterator begin()
	{
		Node* min = _root;
		while (min && min->_left)
		{
			min = min->_left;
		}
		return iterator(min);
	}
	//迭代器结束
	iterator end()
	{
		return iterator(nullptr);
	}

	KeyofT KOT;

	RBTree()
	{}

	RBTree(const RBTree& Tree)
	{
		_root = Copy(Tree._root, nullptr);
	}

	Node* Copy(Node* root, Node* parent)
	{
		if (root == nullptr)
			return nullptr;
		Node* newRoot = new Node(root->_data);
		newRoot->_col = root->_col;
		newRoot->_parent = parent;
		newRoot->_left = Copy(root->_left, newRoot);
		newRoot->_right = Copy(root->_right, newRoot);
		return newRoot;
	}

	~RBTree()
	{
		Destroy(_root);
	}

	void Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

	pair<iterator,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (KOT(data) < KOT(cur->_data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (KOT(data) > KOT(cur->_data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(iterator(cur),false);
			}
		}
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;//新增节点默认红色
		if (KOT(data) > KOT(parent->_data))
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//控制平衡
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			Node* uncle = grandfather->_left;
			if (parent == grandfather->_left)
			{
				uncle = grandfather->_right;
			}
			//情况一：父结点为红，且叔叔结点存在也为红
			if (uncle && uncle->_col == RED)
			{
				//变色，继续向上处理
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = cur->_parent;
			}
			//情况二,三：
			else if (!uncle || uncle->_col == BLACK)
			{
				if (uncle == grandfather->_right)//叔叔结点在右
				{
					if (cur == parent->_left)//cur与parent呈直线则单旋
					{
						RotateR(grandfather);
						//旋转完变色处理
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else //cur与parent呈折线则双旋
					{
						RotateL(parent);
						RotateR(grandfather);
						//旋转完变色
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
				}
				else//叔叔结点在左
				{
					if (cur == parent->_right)//cur与parent呈直线则单旋
					{
						RotateL(grandfather);
						//旋转完变色处理
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else //cur与parent呈折线则双旋
					{
						RotateR(parent);
						RotateL(grandfather);
						//旋转完变色
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					//不用继续向上调整
					break;
				}
			}
			else
			{
				assert(false);
			}
		}
		_root->_col = BLACK;
		return make_pair(iterator(newnode),true);
	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* pparent = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		if (pparent == nullptr)
		{
			_root = subL;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}
		subL->_parent = pparent;
		subL->_right = parent;
		parent->_parent = subL;
		parent->_left = subLR;
		//如果左子树的右子树存在，改变一下它的父节点指针
		if (subLR)
		{
			subLR->_parent = parent;
		}
	}

	//左单旋
	void RotateL(Node* parent)
	{
		Node* pparent = parent->_parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		if (pparent == nullptr)
		{
			_root = subR;
		}
		else
		{
			if (pparent->_right == parent)
			{
				pparent->_right = subR;
			}
			else
			{
				pparent->_left = subR;
			}
		}
		subR->_parent = pparent;
		subR->_left = parent;
		parent->_parent = subR;
		parent->_right = subRL;
		//如果左子树的右子树存在，改变一下它的父节点指针
		if (subRL)
		{
			subRL->_parent = parent;
		}

	}

	//中序遍历
	void InOder()
	{
		_InOder(_root);
	}

	void _InOder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOder(root->_right);
	}

	//检查树
	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{

			return false;
		}
		Node* cur = _root;
		int BenchMark = 0;
		while (cur)
		{
			if (cur->_col == BLACK)
				++BenchMark;
			cur = cur->_left;
		}
		int blacknum = 0;
		return _IsBalance(_root, BenchMark,blacknum);
	}

	bool _IsBalance(Node* root,int BenchMark,int blacknum)
	{
		if (root == nullptr)
		{
			if (BenchMark != blacknum)
			{
				cout << "黑色节点数目不等于基准值" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "出现连续红节点" << endl;
			return false;
		}
		if (root->_col == BLACK)
			++blacknum;
		return _IsBalance(root->_left, BenchMark, blacknum) && _IsBalance(root->_right, BenchMark, blacknum);

	}

private:
		Node* _root = nullptr;
};

